/*
 * 二叉树保存文件和文件缓存链表
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <time.h>

#ifndef PROJECT_C_
 #include "project.h"
#endif
#ifndef UTIL_C_
 #include "util.h"
#endif
#include "binarybuffer.h"

/* 当缓存满时，需要进行替换，将访问次数小与3次并且在内存时间最长删除.暂时删除在内存中最近访问时间最长的 */
#define COUNT_LESS_THAN		3


F_FILE
MakeEmpty (F_FILE T)
{
	if (T != NULL)
	{
		MakeEmpty(T->left);
		MakeEmpty(T->right);
		free_ffile(T);
	}

	return NULL;
}

F_FILE
Find (const char *key_name, F_FILE T)
{
	if (T)
	{
		int key_len = strlen(key_name);
		int t_len = strlen(T->fl_name);
		int len = MAX(key_len, t_len);

		if (memcmp(key_name, T->fl_name, len) < 0)
			return Find(key_name, T->left);
		else if (memcmp(key_name, T->fl_name, len) > 0)
			return Find(key_name, T->right);
	}

	return T;
}

F_FILE
FindMin (F_FILE T)
{
	if (T)
		while (T->left)
			T = T->left;

	return T;
}

F_FILE
FindMax (F_FILE T)
{
	if (T)
		while (T->right)
			T = T->right;

	return T;
}

F_FILE
create_node (const char *key_name, long size, int count)
{
	F_FILE temp; 
	temp = (F_FILE)malloc(sizeof(struct f_file));
	if (temp == NULL)
	{
		sleep(1);
		temp = (F_FILE)malloc(sizeof(struct f_file));
	}
	if (!temp)
	{
		fprintf(stderr, "Out of memory\n");
		exit(3);
	}

	temp->fl_name = strdup(key_name);
	temp->fl_count = count;
	temp->fl_size = size;
	temp->last_access = time(NULL);
	temp->fl_buf = NULL;
	temp->left = temp->right = NULL;

	return temp;
}

F_FILE
Insert (const char *key_name, long size, int count, F_HASH hash)
{
	/* 非递归 */
	if (!(hash->ha_file))
	{
		hash->ha_file = create_node(key_name, size, count);
		return hash->ha_file;
	}
	else
	{
		F_FILE p = hash->ha_file, prev;
		while (p != NULL)
        {
            prev = p;
			p = (strcmp(key_name, p->fl_name) < 0 ? p->left : p->right);
        }
        p = create_node(key_name, size, count);
		if (strcmp(key_name, prev->fl_name) < 0)
            prev->left = p;
        else
            prev->right = p;
		return p;
	}
}

F_FILE
Delete (const char *key_name, F_FILE T)
{
	if (T == NULL)
	{
		fprintf(stderr, "file not exists\n");
		exit(4);
	}

	F_FILE position;
	int key_len = strlen(key_name);
	int t_len = strlen(T->fl_name);
	int len = MAX(key_len, t_len);
	if (memcmp(key_name, T->fl_name, len) < 0)
		T->left = Delete(key_name, T->left);
	else if (memcmp(key_name, T->fl_name, len) > 0)
		T->right = Delete(key_name, T->right);
	else			//found node
	{
		if (T->left && T->right)		//two children
		{
			position = FindMin(T->right);
			free(T->fl_name);
			T->fl_name = strdup(position->fl_name);
			T->fl_count = position->fl_count;
			T->fl_size = position->fl_size;
			T->last_access = position->last_access;
			free_fbuf(T->fl_buf);
			//T->fl_buf = position->fl_buf;
            T->fl_buf = replace_fbuf_strdup(position->fl_buf);
			T->right = Delete(position->fl_name, T->right);
		}
		else			//one child or no child
		{
			position = T;
			if (T->left == NULL)
				T = T->right;
			else if (T->right == NULL)
				T = T->left;
			//free_fbuf(position->fl_buf);
			free_ffile(position);
		}
	}

	return T;
}


/*
 * Done
 */
#ifdef TEST_DELETE_LEAST_BUFFER
char *
Find_Delete_LeastBuf_Proxy (F_FILE *T, double diff)
#else
u_int64_t
Find_Delete_LeastBuf_Proxy (F_HASH hash, double diff)
#endif
{
#ifndef TEST_DELETE_LEAST_BUFFER
	F_FILE T = hash->ha_file;
	F_FILE temp = Find_Delete_LeastBuf(T, diff);
	u_int64_t size = temp->fl_size;
	hash->ha_file = Delete(temp->fl_name, hash->ha_file);
#else
	F_FILE temp = Find_Delete_LeastBuf(*T, diff);
	char *name = strdup(temp->fl_name);
	*T = Delete(temp->fl_name, *T);
#endif

#ifdef TEST_DELETE_LEAST_BUFFER
	return name;
#else
	return size;
#endif
}

/*
 * 替换文件，将缓存中留在内存中时间最长的节点删除
 * @param T 对应二叉树root节点
 */
F_FILE
Find_Delete_LeastBuf (F_FILE T, double diff)
{
	if (T == NULL)
		return NULL;

	F_FILE need_to_be_delete = NULL, left, right;
	double thisDiff = difftime(time(NULL), T->last_access);

	if (thisDiff > diff)
	{
		left = Find_Delete_LeastBuf(T->left, thisDiff);
		right = Find_Delete_LeastBuf(T->right, thisDiff);

		if (!!left && !!right)
			need_to_be_delete = ((T->last_access < left->last_access)
		 						? (T->last_access < right->last_access ? T : right)
		  						: (left->last_access < right->last_access ? left : right));
		else if (!!left)
			need_to_be_delete = (T->last_access < left->last_access) ? T : left;
		else if (!!right)
			need_to_be_delete = (T->last_access < right->last_access) ? T : right;
		else
			need_to_be_delete = T;

	}
	else
	{
		left = Find_Delete_LeastBuf(T->left, diff);
		right = Find_Delete_LeastBuf(T->right, diff);
		if (!!left && !!right)
			need_to_be_delete = (left->last_access < right->last_access) ? left : right;
		else if (!!left)
			need_to_be_delete = left;
		else if (!!right)
			need_to_be_delete = right;
	}

	return need_to_be_delete;
}

/*
 * 检测文件节点是否失效，超过BUFFER_INVALID_TIME则将其从内存中移除
 */
void 
file_node_invalid (F_FILE T, time_t now)
{
	if (T)
	{
		F_FILE position;
		if ((now - T->last_access) >= BUFFER_INVALID_TIME)
		{
			printf("name: %s; difftime: %ld\n", T->fl_name, now-T->last_access);
			position = FindMin(T->right);
			free(T->fl_name);
			free_fbuf(T->fl_buf);
			T->fl_name = strdup(position->fl_name);
			T->fl_count = position->fl_count;
			T->fl_size = position->fl_size;
			T->last_access = position->last_access;
			T->fl_buf = position->fl_buf;
			T->right = Delete(T->fl_name, T->right);
		}

		if (T->left && T->right)
		{
			file_node_invalid(T->right, now);
			file_node_invalid(T->left, now);
		}
		else if (T->left)
			file_node_invalid(T->left, now);
		else if (T->right)
			file_node_invalid(T->right, now);
	}
}

void
free_ffile (F_FILE T)
{
	if (T)
	{
		if (T->fl_name)
			free(T->fl_name);
        if (T->fl_buf)
            free_fbuf(T->fl_buf);

		free(T);
		T = NULL;
	}
}

/*
 * 释放一个文件的所有缓存块，参数必须是f_file指向的第一个缓存块
 */
void
free_fbuf (F_BUF T)
{
	F_BUF for_free;
	while (T)
	{
		for_free = T;
		T = T->next;
		if (for_free->block_buf)
			free(for_free->block_buf);
		free(for_free);
	}
}

void
show_file (F_FILE T)
{
    if (!T)
        return;
    
    printf("%s\n", T->fl_name);
    show_file(T->left);
    show_file(T->right);
}

void
show_innerfix ()
{
    int i;
    for (i = 0; i < 100; i++)
    {
        if (f_hash_arr[i].ha_file)
        {
            //printf("%s\n", f_hash_arr[i].ha_file->fl_name);
            show_file(f_hash_arr[i].ha_file);
        }
    }
    printf("show done\n");
}

/*
 * 得到T的一份拷贝
 */
F_BUF
replace_fbuf_strdup (F_BUF T)
{
    F_BUF ret, back;
    ret = back = NULL;
    if (T)
    {
        ret = (F_BUF) malloc (sizeof(struct f_buf));
        ret->block_buf = strdup(T->block_buf);
        ret->next = NULL;
        back = ret;
        T = T->next;
    }
    while (T->block_buf)
    {
        F_BUF temp = (F_BUF)malloc(sizeof(struct f_buf));
        temp->block_buf = strdup(T->block_buf);
        temp->next = NULL;
        ret->next = temp;
        ret = temp;
        T = T->next;
    }
    F_BUF temp = new(struct f_buf);
    temp->block_buf = NULL;
    temp->next = NULL;
    ret->next = temp;
    
    return back;
}